动态划分的典型问题

动态划分的典型问题

1. 一般背包问题
   假设有m个物品，每个物品质量为 W[ i ]，每个物品的价值为 V[ i ]。
   背包容量为N。
   求能够带走的最大价值为多少。
   每个物品，带走或者不带走，即其标记为1或0；
   假设每次装该物品数量为num[ i ]
   限制条件是，Σ( num[ i ] * W[ i ] ) <=N ，即拿走的物品质量不能超过背包容量。
   dp[j] 表示当背包内容量为j时，其装的最大价值的东西质量为dp[j]。

   ---

   举个例子：
   假设有一个背包容量为10kg，有三个物品，一个为1kg，一个为5kg，一个为7kg，三个价值分别为10,20,15。
   那么容量为1kg，dp[1]=max(10)；2kg，dp[2]=max(10)；3kg…..；5kg，dp[5]=max(v[1]+dp[5-w[0]],dp[4])=max(20,10)=20；以此类推，所以随着j的增长，dp[j]并不是线性增长的，限制条件即为最少需要j>=w[i]，至少取一件物品。

   var bagpro=function(w,v,n){
   	let dp=new Array(n+1);
   	dp.fill(0);
   	for(let i=0;i<w.length;i++){
   		for(let j=n;j>=w[i];j--){
   			dp[j]=Math.max(v[j]+dp[j-w[i]],dp[j]);
   		}
   	}
   	return dp[n];
   }

2. 完全背包问题
   假设每个物品质量为 W[ i ]，每个物品价值为 V[ i ]，物品数量无限。
   背包容量为N，求能够带走的最大价值为多少？
   限制条件是Σ (num[i]*w[i])<=N，此时num[i]取值是非负数即可，因为物品数量不限。

   var completebagpro=function(w,v,n){
   	let dp=new Array(n+1);
   	dp.fill(0);
   	for(let i=0;i<w.length;i++){
   		for(let j=w[i];j<n;j++){
   			dp[j]=Math.max(v[i]+dp[j-w[i]],dp[j]);
   		}
   	}

---

解决动态划分问题最重要的是找到对应的状态转移方程。

例1：零钱问题
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
dp[j]表示组成金额为j的最少硬币数为dp[j]
状态转移方程为：dp[j]=math.min(dp[j-coins[i]]+1,dp[j])

function countcoins(coins,amount){
	let dp=new Array(amount+1);
	dp.fill(0);
	for(let i=0;i<coins.length;i++){
		for(let j=coins[i];j<amount;j++){
			dp[j]=Math.min(1+dp[j-coins[i]],dp[j]);
		}
	}
	if(dp[amount]==0){
		return -1;
	}else{
		return dp[amount];
	}
}

例2：硬币划分
有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？
dp[j]表示组成j分钱有dp[j]种方法。
状态转移方程为：dp[j]=dp[j-coins[0]]+dp[j-coins[1]]+dp[j-coins[2]]+dp[j-coins[3]];
比如说要组成13分，那么去掉一个1分硬币，就是组成12分硬币的种数；去掉一个2分硬币，就是组成11分硬币的种数；以此类推，以上分解情况的和就是组成13分的组合数。

function coinsCombination(coins,n){
	let dp=new Array(n+1).fill(0);
	dp[0]=0;
	for(let i=0;i<coins.length;i++){
		for(let j=coins[i];j<n;j++){
			dp[j]+=dp[j-coins[i]];
		}
	}
	return dp[n]
}